# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution:
    def mergeTwoLists(self, list1: ListNode, list2: ListNode) -> ListNode:
        flag1, flag2 = list1, list2
        Head = ListNode()
        l = Head
        while flag1!=None or flag2!=None:
            if flag1 != None and flag2 != None:
                if flag1.val < flag2.val:
                    l.next = ListNode(val=flag1.val)
                    l = l.next
                    flag1 = flag1.next
                else:
                    l.next = ListNode(val=flag2.val)
                    l = l.next
                    flag2 = flag2.next
            elif flag1 != None:
                l.next = flag1
                break
            elif flag2 != None:
                l.next = flag2
                break
        return Head.next


def PrintList(L: ListNode) -> list:
    flag = L
    vals = list()
    while flag != None:
        vals.append(flag.val)
        flag = flag.next
    print(vals)
    

if __name__ == '__main__':
    s = Solution()
    PrintList(s.mergeTwoLists(list1=ListNode(1, ListNode(2, ListNode(4))), list2=ListNode(1, ListNode(3, ListNode(4)))))
    PrintList(s.mergeTwoLists(list1=None, list2=None))
    PrintList(s.mergeTwoLists(list1=None, list2=ListNode()))
